/*
 * @lc app=leetcode.cn id=1051 lang=java
 *
 * [1051] 高度检查器
 *
 * https://leetcode-cn.com/problems/height-checker/description/
 *
 * algorithms
 * Easy (71.61%)
 * Likes:    35
 * Dislikes: 0
 * Total Accepted:    9.9K
 * Total Submissions: 13.8K
 * Testcase Example:  '[1,1,4,2,1,3]'
 *
 * 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
 *
 * 请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
 *
 *
 *
 * 示例：
 *
 * 输入：[1,1,4,2,1,3]
 * 输出：3
 * 解释：
 * 高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= heights.length <= 100
 * 1 <= heights[i] <= 100
 *
 *
 */

// @lc code=start
class Solution {
    public int heightChecker(int[] heights) {
        int[] h = new int[101];
        int[] people = new int[heights.length];
        for(int n : heights) {
            h[n]++;
        }

        int i = 0;
        for(int index=0; index < h.length; index++) {
            for(int j=0; j < h[index]; j++) {
                people[i++] = index;
            }

        }
        int res = 0;
        for(int index = 0; index < people.length; index++)
            if(people[index] != heights[index])
                res++;
        return res;
    }
}
// @lc code=end

